package com.datastructures2.skipTable;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/9/4 10:32 上午
 */
public class SkipList2 {

    private static final int MAX_LEVEL=16;

    private int levelCount=0;

    private ThreadLocalRandom random=ThreadLocalRandom.current();

    private Node head=new Node();

    public boolean insert(int data){
        int level=randomLevel();
        Node newNode=new Node();
        newNode.data=data;
        newNode.levels=level;

        Node[]update=new Node[level];
        for (int i = 0; i < level; i++) {
            update[i]=head;
        }

        Node p=head;
        //定位到小于data的前一个节点，以便后面进行插入新节点
        for (int i = level-1; i >=0 ; i--) {
            while (p.next[i]!=null && p.next[i].data<data){
                p=p.next[i];
            }
            //如果存在目标值，则不插入
            if (p.next[i]!=null && p.next[i].data==data){
                return false;
            }
            //插入新节点
            update[i]=p;
            newNode.next[i]=update[i].next[i];
            update[i].next[i]=newNode;
        }


        if (level>levelCount){
            levelCount=level;
        }
        return true;
    }
    public Node find(int data){
        Node p=head;
        for (int i = levelCount-1; i >=0 ; i--) {
            while (p.next[i]!=null && p.next[i].data<=data){
                if (p.next[i].data==data){
                    return p.next[i];
                }
                p=p.next[i];
            }
        }
        return null;
    }

    public void delete(int data){
        Node[]update=new Node[levelCount];
        for (int i = 0; i < levelCount; i++) {
            update[i]=head;
        }
        Node p=head;
        for (int i = levelCount-1; i >= 0; i--) {
            while (p.next[i]!=null && p.next[i].data<=data) {
                p = p.next[i];
            }
            update[i]=p;
        }
        for (int i = 0; i < levelCount; i++) {
            if (update[i].next[i]!=null && update[i].next[i].data==data){
                update[i].next[i]=update[i].next[i].next[i];
            }
        }
    }

    public List<Integer> between(int dataFrom, int dataTo){
        Node from = find(dataFrom);
        Node to = find(dataTo);
        List<Integer>result=new ArrayList<>();
        while (from!=null && from.data!=to.data){
            result.add(from.data);
            from=from.next[0];
        }
        result.add(to.data);
        return result;
    }

    private int randomLevel() {
        int level = 0;
        for (int i = 0; i < MAX_LEVEL; i++) {
            if (random.nextInt()%2==0){
                level++;
            }
        }
        return level;
    }


    public class Node{
        public int data=-1;
        public Node[]next=new Node[MAX_LEVEL];
        public int levels;



        @Override
        public String toString() {
            return "{" +
                    "" + data +
                    ", maxLevel=" + levels +
                    '}';
        }
    }
    @Override
    public String toString() {
        Node[]temp=new Node[levelCount];
        for (int i = 0; i <levelCount; i++) {
            temp[i]=head.next[i];
        }
        StringBuilder sb=new StringBuilder();
        for (int i = levelCount-1; i >=0 ; i--) {
            sb.append("第"+i+"层").append(temp[i]).append("\t");
            while (temp[i].next[i]!=null){
                sb.append(temp[i].next[i]).append("\t");
                temp[i]=temp[i].next[i];
            }
            sb.append("\n");
        }
        sb.append("\nlevelCount->"+levelCount);
        return sb.toString();
    }

    public static void main(String[] args) throws InterruptedException {
        List<String>list=new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("3");
        for (String s : list) {
            if (s.equals("3")){
                list.remove(s);
            }
        }
    }
}
class MyList extends ArrayList<String>{

    @Override
    public String[] toArray() {
        return (String[]) new Object[]{"1","2","3"};
    }
}